
// https://leetcode.cn/problems/beautiful-arrangement/description/

// class Solution
// {
//     int cnt;
//     vector<bool> used;
//     int n;

// public:
//     int countArrangement(int _n)
//     {
//         n = _n;
//         used = vector<bool>(n + 1, false);
//         dfs(1);
//         return cnt;
//     }

//     void dfs(int idx)
//     {
//         if(idx > n)
//         {
//             ++cnt;
//             return;
//         }

//         for(int i = 1; i <= n; ++i)
//         {
//             if(used[i] == false && (i % idx == 0 || idx % i == 0))
//             {
//                 used[i] = true;
//                 dfs(idx + 1);
//                 used[i] = false;
//             }
//         }
//     }
// };

class Solution
{
    int cnt;
    char used[16];
    int n;

public:
    int countArrangement(int _n)
    {
        n = _n;
        dfs(1);
        return cnt;
    }

    void dfs(int idx)
    {
        if (idx > n)
        {
            ++cnt;
            return;
        }

        for (int i = 1; i <= n; ++i)
        {
            if (used[i] == 0 && (i % idx == 0 || idx % i == 0))
            {
                used[i] = 1;
                dfs(idx + 1);
                used[i] = 0;
            }
        }
    }
};